package Sort;

/**
 * 排序(5)
 * 快速排序
 */
public class QuickSort extends Template {


    /**
     * 算法P182
     * Comparable[] a    需排序的数组
     * int low 数组头的下标
     * int high 数组尾的下标
     */
    public static void sort(Comparable[] a, int low, int high) {
        if (high <= low) return;//长度为<=1
        int pivotloc = partition(a, low, high);//pivotloc是切分元素下标,将数组一分为二
        sort(a, low, pivotloc - 1);//对左边递归 排序
        sort(a, pivotloc + 1, high);//对右边递归 排序
    }

    private static int partition(Comparable[] a, int low, int high) {
        int i = low, j = high + 1;
        Comparable v = a[low];//基准数据 这里选择数组首位(基准数据随机取)
        //System.out.println("切分元素" + v + " 下标为" + low);
        while (true) {
            //选取小于切分元素的元素
            while (less(a[++i], v)) if (i == high) break;
            //选取大于于切分元素的元素
            while (less(v, a[--j])) if (j == low) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        //show(a);//切分元素还处于参数a首部
        exch(a, low, j);
        //show(a);//切分元素正确位置
        return j;
    }


    public static void main(String[] args) {
        //Comparable[] a = Template.getData(12);
        Comparable[] a = {56, 104, 44, 111, 84, 21, 91, 27, 15, 53, 65, 119};
        System.out.println("快速排序前");

        show(a);

        System.out.println("快速排序过程");
        sort(a, 0, a.length - 1);

        assert isSorted(a);
        System.out.println("快速排序后");
        show(a);

    }

}
